package com.pan.alg.niuke.link;


import java.util.ArrayList;
import java.util.PriorityQueue;

public class MergeKLinkList {

    //用小顶堆，先加上每个ListNode的第一个元素，如果poll，则往后加
    //每次堆调整需要logk，k是链表的数量。堆里维护的数量不会超过k。
    //时间复杂度为O(nlogk)，因为需要遍历到每个节点元素，一共n个。每次调整需要logk
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        //定义链表小顶堆，根据链表值
        PriorityQueue<ListNode> q = new PriorityQueue<>((node1,
                                                         node2) -> (node1.val - node2.val));
        for (ListNode list : lists) {

            q.offer(list);
        }
        //构建一个虚拟节点
        ListNode dummyRoot = new ListNode(-1);
        //定义当前遍历节点
        ListNode current = dummyRoot;
        while (q.size() > 0) {
            ListNode smallest = q.poll();
            current.next = smallest;
            current = current.next;
            //保证加入的不为null
            if (smallest.next != null) {
                q.offer(smallest.next);
            }
        }
        return dummyRoot.next;
    }
}
